// 时间复杂度：O(nlogn)
// 空间复杂度：O(1)
// 不稳定排序

// 基本思想：借用堆结构的排序算法，将数组转为大顶堆，重复从大顶堆取出数值最大的节点，并让剩余的堆结构继续维持大顶堆的性质
// 调整为大顶堆
function heapify(arr, index, end) {
    // 根节点为index，左节点为 2 * index + 1， 右节点为 2 * index + 2
    let left = 2 * index +1
    let right = 2 * index + 2
    while (left <= end) {
        let maxIndex = index
        if (arr[left] > arr[maxIndex]) {
            maxIndex = left
        }
        if (right <= end && arr[right] > arr[maxIndex]) {
            maxIndex = right
        }
        if (index === maxIndex) {
            break
        }
        [arr[index], arr[maxIndex]] = [arr[maxIndex], arr[index]]
        index = maxIndex
        left = 2 * index + 1
        right = 2 * index + 2
    }
}

// 初始化大顶堆
function buildMaxHeap(arr) {
    let size = arr.length
    for (let i = Math.floor(size / 2) ; i >= 0 ; i--) {
        heapify(arr, i, size - 1)
    }
    return arr
}

// 1. 先建立大顶堆
// 2. 让堆顶最大元素与最后一个交换，取最大值，然后调整第一个元素到倒数第二个元素
// 3. 交换堆顶元素与倒数第二个元素，取最大值，调整第一个元素到倒数第三个元素
// 以此类推

function maxHeapSort(arr) {
    buildMaxHeap(arr)
    let size = arr.length
    for (let i = 0; i < arr.length; i++) {
        [arr[0], arr[size - i - 1]] = [arr[size - i - 1], arr[0]]
        heapify(arr, 0, size - i - 2)
    }
    return arr
}

let arr = [2, 7, 26, 25, 19, 17, 1, 90, 3, 36]
console.log(maxHeapSort(arr))